selection problem

problem

共N個數字取第 K 大的數字。

Input:

一堆數字 (N個)、 K

Output:

第 K 大的數字

solution

做好排序(大到小)

approach 1 / 簡單但須處理過所有數字

一堆數字塞array，排大小，要第 K 大就在 K 位置

approach 2 / Array大小就只有 K，只要對 K 個作排序

一堆數字中取 K 個數字進 array 排序，從未選取的數字裡和 array 中第 K 個數字比較

• 比第 K 個數字小: 不理他
• 比第 K 個數字大: 有機會進來，看要放哪個位置

============================================================

note:

時間上來說 排序 會差很多，但 是比對 不會差很多，試想 approach 1 和 approach 2 如果 N >> K，那方法的好壞差距就出來囉!